1. Field of the Invention
The present invention relates generally to high speed digital logic circuitry in which digital signal propagation delay is greatly reduced. The invention is applicable to any serial connection of digital logic circuits, such as carry circuits and to multiplexers in series. The invention is particularly applicable to associative processors in which large numbers of carry circuits or multiplexers are connected in series.
2. Description of the Prior Art
It is known in the art that it is advantageous to minimize the number of connections between arithmetic cells in a processor, such as an associative processor, in order to minimize interconnection and propagation delay problems. The typical arithmetic adder implementation, a carry look ahead circuit, requires many data paths, so it cannot always be effectively used where fast execution time is required. No such look ahead technique exists in the known prior art for a circuit with a large number of multiplexers in series.
Another known solution to carry circuits is the Manchester carry circuit, which takes advantage of the "pass transistor" structure in MOS circuits. A pass transistor, which simply passes its input to its output, in each bit of an adder, is turned on when the carry into a bit should be propagated to the carry out of the bit, i.e. when only one of the two parallel inputs to the adder is true. A carry into the cell can thus be rapidly directed to the carry output of the cell because all of the carry propagate decisions can be made simultaneously, by a circuit that looks at the parallel inputs to the adder. The drawback of this known technique is the relatively high impedance of the pass transistor in the active state. As the number of bits through which carry is propagated increases, the distributed capacitance, along with the increasing impedance of the string of pass transistors, greatly slows down circuit operation.
Associative processors are processors which operate on many data objects simultaneously rather than sequentially as in a conventional processor. Such an associative processor may be comprised of an array of single bit computers implemented in LSI. Such cellular computers obey the same instruction simultaneously, each operating on its own data.
The cells in a row of the associative processor array can be dynamically (from one instruction to the next) configured into an arbitrary number of fields of arbitrary defined length (within the constraints of the width of the array). Each field can then operate independently as if it were a separate computer of the given word length, able to perform arithmetic and logical operation. These fields can all obey the same instruction simultaneously, or they may be selectively disabled under program control.
An example of an associative processor cell architecture of the type which may effectively utilize the present invention is described by the cross-referenced copending application Ser. No. 404,242 to which reference may be made for details of an associative processor; however, it is to be understood that the present invention is applicable to other associative processor structures.
U.S. Pat. No. 3,728,532, Carry Skip-Ahead Network, describes carry networks having a power-of-2 number of bits in which the number of connections between cells increases as the number of skipped bits increases, being four for a 4-bit block, thus increasing the cost of interconnection. U.S. Pat. No. 3,654,394, Field Effect Transistor Switch, Particularly for Multiplexing, described multiplexing analog signals. U.S. Pat. No. 3,925,651, Current Mode Arithmethic Logic Array shows a 4-bit arithmetic and logical unit built of current mode logic. U.S. Pat. No. 4,229,803, I.sup.2 L Full Adder and ALU, shows an I.sup.2 L arithmetic and logic unit.